package swardToOffer.struct_2_string;

import java.util.Arrays;
import java.util.Objects;

/**
 * @Author ChanZany
 * @Date 2021/5/19 17:10
 * @Version 1.0
 * 请实现一个函数，把字符串中的每个空格替换成"%20"，例如
 * 输入"we are happy",则输出"we%20are%20happy"
 * 方案1(不推荐):从前往后遍历每个char，当遇到空格则将当前下标及之后的所有元素后移三个单元格，然后在当前单元格和后两个单元格放入 '%' '2' '0'
 * 方案2（推荐）：改变思路，方案1从前往后没遇到一个空空格都要移动大量字符，低效，那么从后往前呢？
 * 1. 统计字符串中空格的总数m，计算出替换空格后的字符串长度n
 * n = n + m*2
 * 2. 从字符串的后面开始复制和替换，需要辅助指针的帮助
 * P1 指向原始字符串的末尾
 * P2 指向替换后的字符串的末尾
 */
public class ReplaceBlank {
    private char[] replaceBlank(char[] chs) {
        if (chs.length <= 0) return null;
        int originalLength = 0, numberOfBlank = 0;
        for (char ch : chs) {
            originalLength++;
            if (ch == ' ') numberOfBlank++;
        }
        int newLength = originalLength + numberOfBlank * 2;
        int p1 = originalLength - 1;//指向原始字符串的末尾
        int p2 = newLength - 1;     //指向替换后的字符串的末尾
        chs = Arrays.copyOf(chs, newLength);
        while (p1 >= 0 && p2 > p1) {
            if (chs[p1] == ' ') {
                chs[p2--] = '0';
                chs[p2--] = '2';
                chs[p2--] = '%';
            } else {
                chs[p2--] = chs[p1];
            }
            p1--;
        }
        return chs;
    }

    public static void main(String[] args) {
        ReplaceBlank replaceBlank = new ReplaceBlank();
        char[] chs = "we are happy".toCharArray();
        System.out.println(Objects.requireNonNull(replaceBlank.replaceBlank(chs)));

    }

}
